#include <iostream>
#include <fstream>
#include <cstdlib>
#include <iomanip>
#include <string>
#include <vector>
#include <sstream>
#include <time.h>
#include <map>
#include <set>
//#include <conio.h>
#pragma warning(disable:4786)

//pattern,³B²zTID
using namespace std;

//global function
inline string int2string(int n) {
	stringstream ss;
	string temp;
	ss << n;
	ss >> temp;
	return temp;
}

inline int string2int(string s) {
	istringstream strin(s);
	int i;
	strin >> i;
	return i;
}

//=====================================================================================

// store  the x and y coorinate of the point
struct location {
	int x;
	int y;
};

// the coorindate and the correspondence timestamp, the basic data element in the trajectory
struct SequenceNode {
	location coordinate;
	int timestamp;
};

//=====================================================================================

// the basic element of the database, a set of a series of SequenceNode
class Sequence {
	friend class SequenceDatabase;

public:
	string TID;
	vector<SequenceNode> List;

	Sequence(); //default constructor
	~Sequence(); //destructor

	void addSequenceNode(SequenceNode node); //add a SequenceNode into the List(at the end of the list)
	void deleteSequenceNode(int index); //Delete the SequenceNode by it index in the List
	SequenceNode at(int index); //specific the SequenceNode by it index in the List
	int length(); //return the total numberof SequenceNode in the List
	void clear(); //delete all the SequenceNode of the List
	void destroy(); //call the distrctor of the List(different with the clear)

};

Sequence::Sequence() {
	TID = "";
	List.clear();
}

Sequence::~Sequence() {
}

void Sequence::addSequenceNode(SequenceNode node) {
	List.push_back(node);
}

void Sequence::deleteSequenceNode(int index) {
	List.erase(List.begin() + index);
}

SequenceNode Sequence::at(int index) {
	return List.at(index);
}

int Sequence::length() {
	return List.size();
}

void Sequence::clear() {
	List.clear();
	TID = "";
}

void Sequence::destroy() {
	List.~vector();
	TID = "";
}

//=====================================================================================

//The Transaction of the Projected Database
struct ProjectedTransaction {
	int TID; //­×§ï												  //The correspondence TID of the Original Database( the index of the OrgDatabase vector)
	int index_Node; //The correspondence index of the Sequence of the Original Database( the index of the Sequence)
};

//The freuquent 1 items
struct frequent {
	location pattern; //The freuquent item of the original database
	int count; //the total occurence of the frequenct item int the Original Databas(OrgDatabase)
};

//The frequent item without freuquent 1 items
struct Projectedfrequent {
	location pattern; //The frequenct item of the projected database
	int timespan; //The timespan between 2 frequent pattern
	set<int> TIDset; //to avoid support overcounting
	vector<ProjectedTransaction> projectedDB; //The correspondence further Projected database
	int count; //The count of the frequent item
};

//=====================================================================================

class SequenceDatabase {
public:
	int tuplesScanned;
	int candidates;
	int candidatesarry [4];
	int minimumsupport; //user definded mininimum support
	int maximumtimespan; //user definded maximum time span
	int numberoftransaction; //the number of Sequence in the database

	int numberofP; //the counter of frequent pattern;
	string filename; //the output file name
	string pattern; //a part of a pattern
	string apattern; //a full length pattern

	vector<Sequence> OrgDatabase; //the database which we are mined
	map<string, int> sup_index; //map the location to a specific index of sup
	vector<frequent> sup; //save the count of the orginial database frequent 1
	vector<string> patterns; //the vector which store all frequent fattern
	//map< string, int > TID_DBIndex;                                       //transfer the TID of the sequence to the DB index
	//map< int, string > DBIndex_TID;                                       //transfer the DB index to the TID of the sequence

	SequenceDatabase(int Min_Support, int Max_TimeSpan); //constructor
	~SequenceDatabase(); //destructor

	void addTransaction(Sequence seq); //add the sequence into the OrgDatabase
	vector<frequent>* findfrequent(vector<Sequence>* orgDB); //extract the frequent item in the origianl databse and store them into the sup

	vector<ProjectedTransaction> project(frequent* frequentset,
			vector<Sequence>* orgDB);
	//project teh original database with the frequent pattern
	void project(vector<ProjectedTransaction>* DB);

	int size(); //return the number of transaction of the databse
	void destroy();

};

SequenceDatabase::SequenceDatabase(int Min_Support, int Max_TimeSpan) //constructor
{
	minimumsupport = Min_Support;
	maximumtimespan = Max_TimeSpan;
	numberofP = 0; //initalize the number of freuquent pattern
	tuplesScanned = 0;
	candidates = 0;
	candidates = 0;
	pattern = ""; //initalize a output string
	apattern = ""; //initalize a output string
	filename = "P-S" + int2string(Min_Support) + "T" + int2string(Max_TimeSpan)
			+ ".data";
	//initalize a output file name
	ofstream ResultFile(filename.c_str(), ios_base::out); //initalize the output stram

	if (!ResultFile) {
		cerr << "File could not be opened" << endl;
		exit(1);
	}
	//print the 2 paramaters in the file
	ResultFile << "The Maximum Time Span is: " << int2string(Max_TimeSpan)
			<< endl;
	ResultFile << "The Minimum Support is : " << int2string(Min_Support)
			<< endl;
	ResultFile.close();
}

void SequenceDatabase::addTransaction(Sequence seq) //add the sequence into the OrgDatabase
{
	OrgDatabase.push_back(seq);
}

int SequenceDatabase::size() //return the number of transaction of the OrgDatabase
{
	return OrgDatabase.size();
}

//find the frequent 1 items (location) in the orginaial database whcih don't need to consider the time span
vector<frequent>* SequenceDatabase::findfrequent(vector<Sequence>* orgDB) {
	set<string> check; //save all item of a sequence in order to avoid over counting the support(same items/patterns occur twice in the sequence)
	string index_key = ""; //the index of sup_index
	int index = 0; //the index of the support vector that use in matching the item/index->index/count

	for (int D = 0; D < (orgDB->size()); D++) //for all sequence in the database
	{
		check.clear(); //initalize the check set for every sequence frequenct item finding
		for (int s = 0; s < orgDB->at(D).length(); s++) //for all item in a seuquence
		{
			tuplesScanned++;
			index_key = int2string(orgDB->at(D).at(s).coordinate.x) + ","
					+ int2string(orgDB->at(D).at(s).coordinate.y);
			//convert the item/location as a string

			if (sup_index.find(index_key) != sup_index.end()) //check if the item has been existed in the sup, if it isn't exist, return the sup_index.end()
			{
				if (check.find(index_key) == check.end()) //check if the same item has been existed in a sequence
				{
					check.insert(index_key); //update the check set if item has not existed before
					sup[sup_index[index_key]].count++; //update the count of a item
				}
			} else {
				sup_index.insert(make_pair(index_key, index)); //add a new item/index pair of the support count vector
				check.insert(index_key); //update the check set if item has not existed before

				frequent candidate; //new a candiate frequent
				candidate.pattern.x = orgDB->at(D).at(s).coordinate.x; //the x coordinate of the first place which it exist of the pattern
				candidate.pattern.y = orgDB->at(D).at(s).coordinate.y; //the y coordinate of the first place which it exist of the pattern
				candidate.count = 1; //update the count of a item
				sup.push_back(candidate); //add the new item into the support vector
				index++; //update the index of the sup
			}
		}
	} //end of finding the frequent location in the orginal database
	candidates += sup.size();
	candidatesarry[0] = sup.size();
	//the frequent items with its count are stored in sup vector and sup_index
	for (int c = sup.size() - 1; c >= 0; c--) //checking all the item count of the sup
	{
		if (sup[c].count < minimumsupport) //if the count of the item less than minimumsupport
			sup.erase(sup.begin() + c); //delete the infrequent item in the sup
	}

	return &sup;

} //after that, we find all the frequent 1 item and add it the sup vector which contatin the pointer of the item and its count

//project the original database with the frequent 1 item whcih don't need to consider the tiem span
vector<ProjectedTransaction> SequenceDatabase::project(frequent* frequentitem,
		vector<Sequence>* orgDB) //in original database
{
	vector<ProjectedTransaction> projectedDB; //the output vector

	for (int D = 0; D < orgDB->size(); D++) //for every transaction of the orgDB
	{
		for (int s = 0; s < orgDB->at(D).length(); s++) //for every item in a sequence
		{
			tuplesScanned++;
			if ((frequentitem->pattern.x == orgDB->at(D).at(s).coordinate.x)
					&& (frequentitem->pattern.y
							== orgDB->at(D).at(s).coordinate.y)) { //find the index of the seuquence which the item is same with the frequenitem
				ProjectedTransaction data; //new a projected sequence
				data.TID = D;
				data.index_Node = s + 1;
				projectedDB.push_back(data); //add the projected sequence into the projected database
			}
		}
	}

	return projectedDB; //return the freuqnet 1 item projected database, pass by value
}

//further project in the further projected database which need to consider the time span
void SequenceDatabase::project(vector<ProjectedTransaction>* projDB) {
	pattern = ""; //initalize a output string
	apattern = ""; //initalize a output string
	location projnode = { -1, -1 };
	int timestamp = 0; //record the timestamp of the 1st item of the projected sequence
	int timespan = 0; //record the timespan of the pervious frequent item and the first item of the projected sequence
	int index = 0; //index of the count vector of the projected database

	map<string, int> sup_index; //new a map of item/index pair
	string index_key = ""; //initalize the item of the item/index pair map

	vector<Projectedfrequent> sup; //the vector of the frequent item of the projected database which contian the item count, the further projected data base

	//generate the item support of the projected database
	for (int D = 0; D < projDB->size(); D++) //check every sequence in the projected database
	{
		tuplesScanned++;
		if ((projDB->at(D).index_Node)
				!= OrgDatabase.at(projDB->at(D).TID).length()) {
			projnode = OrgDatabase.at(projDB->at(D).TID).at(
					(projDB->at(D).index_Node)).coordinate;
			//project the next node of the projected database
			timestamp = OrgDatabase.at(projDB->at(D).TID).at(
					(projDB->at(D).index_Node)).timestamp;
			//get the time stamp of the next sequence node
			timespan = timestamp - OrgDatabase.at(projDB->at(D).TID).at(
					(projDB->at(D).index_Node) - 1).timestamp;
			//caculate the timespan
			index_key = int2string(timespan) + "<" + int2string(projnode.x)
					+ "," + int2string(projnode.y) + ">";
			//transfer the timespan and item combination as a index_key of the sup_index map
			if (timespan <= maximumtimespan) //if the timespan constrain is satisifed
			{
				if (sup_index.find(index_key) != sup_index.end()) //check if the same "timespan+location" index_key has been exist (from many sequence)
				{
					if (sup[sup_index[index_key]].TIDset.find(projDB->at(D).TID)
							== sup[sup_index[index_key]].TIDset.end()) { //check if the same pattern come from the same TID(sequence)
						sup[sup_index[index_key]].TIDset.insert(
								projDB->at(D).TID);
						//update the TIDset
						sup[sup_index[index_key]].count++; //update the count of the longer pattern
					}
					ProjectedTransaction data;
					data.TID = projDB->at(D).TID;
					data.index_Node = projDB->at(D).index_Node + 1;
					//new a projected transaction with the same TID and one further index(consecutive constrain)
					sup[sup_index[index_key]].projectedDB.push_back(data);
					//add it into the correspondence PojectedDB
				} else {
					sup_index.insert(pair<string, int> (index_key, index)); //create a new item/index pair
					Projectedfrequent candidate; //new a projectedfrequenct obejct
					candidate.pattern = projnode; //set pattern as the first item of the projected transaction
					candidate.TIDset.insert(projDB->at(D).TID); //update the TIDset
					candidate.count = 1; //update the count of the lngerpattern
					candidate.timespan = timespan; //record the timesapn to output
					ProjectedTransaction data;
					data.TID = projDB->at(D).TID;
					data.index_Node = (projDB->at(D).index_Node) + 1;
					//new a projected transaction with the same TID and one further index(consecutive constrain)
					candidate.projectedDB.push_back(data); //add the projected transaction in the ProjectedDB

					sup.push_back(candidate); //add the new projected frequent in the sup vector

					index++; //update the index
				}
			}
		}
	}
	candidates += sup.size();
	candidatesarry[min((int)patterns.size(),3)]+=sup.size();
	/*
	 map< string, int >::iterator iter;
	 for( iter = sup_index.begin(); iter != sup_index.end(); iter++ )
	 {
	 cout << projnode.x << "," << projnode.y << endl;
	 cout << "word: " << iter->first << ", index: " << iter->second << ", count: " << sup[iter->second].count << endl;
	 }
	 */

	//find the frequent items and output the pattern to a file
	for (int c = 0; c < sup.size(); c++) //for every smaller projected database
	{
		if (sup[c].count >= minimumsupport) //if the count is bigger than or equal to minimumsupoort
		{
			//cout << sup[c].count << ": ";
			pattern = int2string(sup[c].timespan) + "(" + int2string(
					sup[c].pattern.x) + "," + int2string(sup[c].pattern.y)
					+ ")";
			//cout << pattern << endl;
			patterns.push_back(pattern);

			for (int printall = 0; printall < patterns.size(); printall++) {
				apattern += patterns.at(printall);
			}

			apattern += "\n";
			numberofP++; //increase the number of frequent pattern
			//cout << apattern ;

			ofstream ResultFile(filename.c_str(), ios_base::out | ios::app);
			//output the pattern to the output file
			if (!ResultFile) {
				cerr << "File could not be opened" << endl;
				exit(1);
			}

			ResultFile.clear();
			ResultFile.seekp(ios_base::end);
			ResultFile << int2string(numberofP) << "." << apattern;
			ResultFile.close();

			project(&sup[c].projectedDB); //recursive project it
			patterns.pop_back();
		}
	}
}

void SequenceDatabase::destroy() {

}

//===========================================================================================
int main(int argn, char** argv) {
	//input the user predifined variable
	int Min_Support, Max_TimeSpan;

	string inputfile = string(argv[1]);
	Min_Support = string2int(string(argv[2]));
	Max_TimeSpan = string2int(string(argv[3]));

	//start of recording the total time
	clock_t start, finish;
	double totaltime;
	start = clock();

	// new Reference space
	SequenceDatabase* DB = new SequenceDatabase(Min_Support, Max_TimeSpan);

	//read the data from the file Inputfile
	char ch, ch1 = '?';
	string content = "", contentx = "", contenty = "", contentt = ""; //<x,y,t>
	location coordinate; //object predefined
	SequenceNode record; //object predefined
	Sequence transaction; //object predefined
	vector<ProjectedTransaction> ProjectedDB; //object - Projected DB
	vector<frequent>* freqvector; //the pointer of the frequent 1 items

	ifstream inSampleFile(inputfile.c_str(), ios::in);

	if (!inSampleFile) {
		cerr << "File could not be opened" << endl;
		exit(1);
	}

	while (inSampleFile.get(ch)) {
		switch (ch) {
		case '<':
			ch1 = '<';
			contentx = "";
			break;
		case ',':
			if (ch1 == ',') {
				ch1 = '*';
				contentt = "";
			} else {
				ch1 = ',';
				contenty = "";
			}
			break;
		case '>':
			ch1 = '>';
			break;
		case '|':
			ch1 = '|';
			break;
		case '?':
			ch1 = '?';
			transaction.TID = content; //add the TID to the sequence
			//DB->TID_DBIndex.insert(make_pair(content,DB->size()));    //match the Sequence TID to the DB OrgDB
			//DB->DBIndex_TID.insert(make_pair(DB->size(),content));    //match the DB orgDb index to Sequecne TID
			DB->addTransaction(transaction); //add the transaction into the database
			transaction.clear(); //clear the content of the sequence avoid new a sequence continuously
			content = "";
			break;
		}

		if ((ch1 == '?') && (ch != '?')) {
			content += ch; //tid of the sequence is the index of the database
		}

		if ((ch1 == '<') && (ch != '<')) {
			contentx += ch;
		}

		if ((ch1 == ',') && (ch != ',')) {
			contenty += ch;
		}

		if ((ch1 == '*') && (ch != ',')) {
			contentt += ch;
		}

		//add SequenceNode in a Sequence, contentx and contty represent the specific coordinates of a location item
		if (ch == '>') //
		{
			coordinate.x = string2int(contentx); //fill the data into the object of x
			coordinate.y = string2int(contenty); //fill the data into the object	of y
			record.coordinate = coordinate; //fill the data into the object
			record.timestamp = string2int(contentt); //fill the data into the object
			transaction.addSequenceNode(record); //add the data into the transaction
		}

	}

	//all the data is stored in DB
	inSampleFile.close();

	//find frequent 1
	freqvector = DB->findfrequent(&(DB->OrgDatabase));

	//project in the orginal database
	for (int f = 0; f < (freqvector->size()); f++) {
		DB->pattern = "(" + int2string(freqvector->at(f).pattern.x) + ","
				+ int2string(freqvector->at(f).pattern.y) + ")";
		DB->patterns.push_back(DB->pattern);
		DB->apattern = DB->pattern + "\n";

		DB->numberofP++; //increase the number of frequent pattern
		//cout << (DB->apattern) ;

		ofstream ResultFile(DB->filename.c_str(), ios_base::out | ios::app);
		//output the pattern to the output file
		if (!ResultFile) {
			cerr << "File could not be opened" << endl;
			exit(1);
		}

		ResultFile.clear();
		ResultFile.seekp(ios_base::end);
		ResultFile << int2string(DB->numberofP) << "." << DB->apattern;
		ResultFile.close();

		ProjectedDB = DB->project(&(freqvector->at(f)), &(DB->OrgDatabase));
		//for every frequent 1 item, project the orginal database DB
		DB->project(&ProjectedDB);
		DB->patterns.pop_back();
	}

	//output the result to the file
	ofstream ResultFile(DB->filename.c_str(), ios_base::out | ios::app);

	if (!ResultFile) {
		cerr << "File could not be opened" << endl;
		exit(1);
	}
	ResultFile << "The number of trajectory pattern is : " << int2string(
			DB->numberofP) << endl;
	ResultFile.close();

	cout << int2string(DB->numberofP) << endl;

	// end of recording the total time
	finish = clock();
	totaltime = (double) (finish - start) / CLOCKS_PER_SEC;
	cout << "Number of candidates:" << DB->candidates << endl;
	cout << "Number of 1-pattern candidates:" << DB->candidatesarry[0] << endl;
	cout << "Number of 2-pattern candidates:" << DB->candidatesarry[1] << endl;
	cout << "Number of 3-pattern candidates:" << DB->candidatesarry[2] << endl;
	cout << "Number of long pattern candidates:" << DB->candidatesarry[3] << endl;
	cout << "Number of tuples scanned:" << DB->tuplesScanned << endl;
	cout << "Total time is " << totaltime << "s" << endl;

	//    getch();
	return 0;

}

